
interface ListNode<T> {
    val: T;
    next: ListNode<T>
}

function mergeKLists(lists: ListNode<number>[]): ListNode<number> {

    if (lists.length === 0) return null;
    if (lists.length === 1) return lists[0];
    if (lists.length === 2) {
        var [l1, l2] = lists;
    }
    else {
        const middle = Math.floor(lists.length / 2);
        l1 = mergeKLists( lists.slice(0, middle));
        l2  = mergeKLists(lists.slice(middle));        
    }

    let head: ListNode<number> = { val: -1, next: null };
    let tail = head;
    while(l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        }
        else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    if (l1 !== null && l2 === null) tail.next = l1;
    else tail.next = l2;
    return head.next;        
};

function convertToKList(xs: number[][]) {
    var result: ListNode<number>[] = [];
    for(var ys of xs) {
        var head: ListNode<number> = null
        for(var y of ys.reverse()) {
            head = { val: y, next: head}
        }
        result.push(head);
    }
    return result;
}

function convertFromKList(head: ListNode<number>, size: number): number[] {
    var result: number[] = new Array(size);
    var i = 0;
    while(head !== null) {
        result[i] = head.val;
        head = head.next;
        i++;
    }
    return result;
}

var input: ListNode<number>[];

var xss: number[];

xss = 
    convertFromKList( 
        mergeKLists( 
            convertToKList( [ 
                [ 10, 11 ], 
                [ 1, 2 ] 
            ])
        ),
        4
    );

xss = 
    convertFromKList( 
        mergeKLists( 
            convertToKList( [ 
                [ 42 ] 
            ])
        ),
        1
    );

xss = 
    convertFromKList( 
        mergeKLists( 
            convertToKList( [ 
            ])
        ),
        0
    );

xss = 
    convertFromKList( 
        mergeKLists( 
            convertToKList( [ 
                [ 1 ],
                [ 0 ]
            ])
        ),
        2
    );

input = convertToKList( [ 
                [-6,-4,0,0,4],[],[-4,-2,-1,1,2,3],[-9,-6,-5,-2,4,4],[-9,-6,-5,-2,-1,3],[-2,-1,0],[-6],[-8,-1,0,2]
            ]);

xss = convertFromKList( mergeKLists(input), 100);

xss = 
    convertFromKList( 
        mergeKLists( 
            convertToKList( [ 
                [2],[],[-1]
            ])
        ),
        2
    );

console.log('happy end');